package org.example.SolutionNew006;

public class BinarySearch002 {
    public static void main(String[] args) {
        BinarySearch002 obj = new BinarySearch002();
        int[][] matrix={{1}};
        System.out.println(obj.searchMatrix(matrix, 0));

    }

    public boolean searchMatrix1(int[][] matrix, int target) {
        //暴力
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        //两次二分
        int m=matrix.length,n=matrix[0].length;

        //第一次二分找在哪一行
        int start=-1,end=m-1;
        while(start<end){
            int mid=start+(end-start+1)/2;
            if(matrix[mid][0]<=target){
                start=mid;
            }else{
                end=mid-1;
            }
        }

        if(start==-1) return false;

        int left=0,right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(matrix[start][mid]==target){
                return true;
            }else if(matrix[start][mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return false;
    }

    public boolean searchMatrix3(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        int start=0,end=m*n-1;
        while(start<=end){
            int mid=start+(end-start)/2;
            if(matrix[mid/n][mid%n]==target){
                return true;
            }else if(matrix[mid/n][mid%n]<target){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        int x=0,y=n-1;
        while(x<m&&y>=0){
            if(matrix[x][y]==target){
                return true;
            }else if(matrix[x][y]<target){
                x++;
            }else{
                y--;
            }
        }
        return false;
    }

}
